home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / utilities / text / less-278.lha / less-278 / src.lha / source / search.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-01  |  24.0 KB  |  1,183 lines
  1. /*
  2.  * Copyright (c) 1984,1985,1989,1994,1995  Mark Nudelman
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice in the documentation and/or other materials provided with 
  12.  *    the distribution.
  13.  *
  14.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY
  15.  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
  17.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE
  18.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
  19.  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
  20.  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
  21.  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
  22.  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
  23.  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 
  24.  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25.  */
  26.  
  27.  
  28. /*
  29.  * Routines to search a file for a pattern.
  30.  */
  31.  
  32. #include "less.h"
  33. #include "position.h"
  34.  
  35. #define    MINPOS(a,b)    (((a) < (b)) ? (a) : (b))
  36. #define    MAXPOS(a,b)    (((a) > (b)) ? (a) : (b))
  37.  
  38. #if HAVE_POSIX_REGCOMP
  39. #include <regex.h>
  40. #endif
  41. #if HAVE_RE_COMP
  42. char *re_comp();
  43. int re_exec();
  44. #endif
  45. #if HAVE_REGCMP
  46. char *regcmp();
  47. char *regex();
  48. extern char *__loc1;
  49. #endif
  50. #if HAVE_V8_REGCOMP
  51. #include "regexp.h"
  52. #endif
  53. #if NO_REGEX
  54. static int match();
  55. #endif
  56.  
  57. extern int sigs;
  58. extern int how_search;
  59. extern int caseless;
  60. extern int linenums;
  61. extern int sc_height;
  62. extern int jump_sline;
  63. extern int bs_mode;
  64. #if HILITE_SEARCH
  65. extern int hilite_search;
  66. extern int screen_trashed;
  67. extern int size_linebuf;
  68. static int hide_hilite;
  69. static POSITION prep_startpos;
  70. static POSITION prep_endpos;
  71.  
  72. struct hilite
  73. {
  74.     struct hilite *hl_next;
  75.     POSITION hl_startpos;
  76.     POSITION hl_endpos;
  77. };
  78. static struct hilite hilite_anchor = { NULL };
  79. #endif
  80.  
  81. /*
  82.  * These are the static variables that represent the "remembered"
  83.  * search pattern.  
  84.  */
  85. #if HAVE_POSIX_REGCOMP
  86. static regex_t *regpattern = NULL;
  87. #endif
  88. #if HAVE_RE_COMP
  89. int re_pattern = 0;
  90. #endif
  91. #if HAVE_REGCMP
  92. static char *cpattern = NULL;
  93. #endif
  94. #if HAVE_V8_REGCOMP
  95. static struct regexp *regpattern = NULL;
  96. #endif
  97. #if NO_REGEX
  98. static char *last_pattern = NULL;
  99. #endif
  100.  
  101. static int is_caseless;
  102. static int is_ucase_pattern;
  103.  
  104. /*
  105.  * Convert text.  Perform one or more of these transformations:
  106.  */
  107. #define    CVT_TO_LC    01    /* Convert upper-case to lower-case */
  108. #define    CVT_BS        02    /* Do backspace processing */
  109.  
  110.     static void
  111. cvt_text(odst, osrc, ops)
  112.     char *odst;
  113.     char *osrc;
  114.     int ops;
  115. {
  116.     register char *dst;
  117.     register char *src;
  118.  
  119.     for (src = osrc, dst = odst;  *src != '\0';  src++, dst++)
  120.     {
  121.         if ((ops & CVT_TO_LC) && isupper(*src))
  122.             /* Convert uppercase to lowercase. */
  123.             *dst = tolower(*src);
  124.         else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
  125.             /* Delete BS and preceding char. */
  126.             dst -= 2;
  127.         else 
  128.             /* Just copy. */
  129.             *dst = *src;
  130.     }
  131.     *dst = '\0';
  132. }
  133.  
  134. /*
  135.  * Are there any uppercase letters in this string?
  136.  */
  137.     static int
  138. is_ucase(s)
  139.     char *s;
  140. {
  141.     register char *p;
  142.  
  143.     for (p = s;  *p != '\0';  p++)
  144.         if (isupper(*p))
  145.             return (1);
  146.     return (0);
  147. }
  148.  
  149. /*
  150.  * Is there a previous (remembered) search pattern?
  151.  */
  152.     static int
  153. prev_pattern()
  154. {
  155. #if HAVE_POSIX_REGCOMP
  156.     return (regpattern != NULL);
  157. #endif
  158. #if HAVE_RE_COMP
  159.     return (re_pattern != 0);
  160. #endif
  161. #if HAVE_REGCMP
  162.     return (cpattern != NULL);
  163. #endif
  164. #if HAVE_V8_REGCOMP
  165.     return (regpattern != NULL);
  166. #endif
  167. #if NO_REGEX
  168.     return (last_pattern != NULL);
  169. #endif
  170. }
  171.  
  172. #if HILITE_SEARCH
  173. /*
  174.  * Repaint the hilites currently displayed on the screen.
  175.  * Repaint each line which contains highlighted text.
  176.  * If on==0, force all hilites off.
  177.  */
  178.     public void
  179. repaint_hilite(on)
  180.     int on;
  181. {
  182.     int slinenum;
  183.     POSITION pos;
  184.     POSITION epos;
  185.     int save_hide_hilite;
  186.     extern int can_goto_line;
  187.  
  188.     save_hide_hilite = hide_hilite;
  189.     if (!on)
  190.     {
  191.         if (hide_hilite)
  192.             return;
  193.         hide_hilite = 1;
  194.     }
  195.  
  196.     if (!can_goto_line)
  197.     {
  198.         repaint();
  199.         hide_hilite = save_hide_hilite;
  200.         return;
  201.     }
  202.  
  203.     for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
  204.     {
  205.         pos = position(slinenum);
  206.         if (pos == NULL_POSITION)
  207.             continue;
  208.         epos = position(slinenum+1);
  209.         /*
  210.          * If any character in the line is highlighted, 
  211.          * repaint the line.
  212.          */
  213.         if (is_hilited(pos, epos, 1))
  214.         {
  215.             (void) forw_line(pos);
  216.             goto_line(slinenum);
  217.             put_line();
  218.         }
  219.     }
  220.     hide_hilite = save_hide_hilite;
  221. }
  222. #endif
  223.  
  224. /*
  225.  * Hide search string highlighting.
  226.  */
  227.     public void
  228. undo_search()
  229. {
  230.     if (!prev_pattern())
  231.     {
  232.         error("No previous regular expression", NULL_PARG);
  233.         return;
  234.     }
  235. #if HILITE_SEARCH
  236.     hide_hilite = !hide_hilite;
  237.     repaint_hilite(1);
  238. #endif
  239. }
  240.  
  241. /*
  242.  * Compile a search pattern, for future use by match_pattern.
  243.  */
  244.     static int
  245. compile_pattern(pattern)
  246.     char *pattern;
  247. {
  248. #if HAVE_POSIX_REGCOMP
  249.     regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
  250.     if (regcomp(s, pattern, 0))
  251.     {
  252.         free(s);
  253.         error("Invalid pattern", NULL_PARG);
  254.         return (-1);
  255.     }
  256.     if (regpattern != NULL)
  257.         regfree(regpattern);
  258.     regpattern = s;
  259. #endif
  260. #if HAVE_RE_COMP
  261.     PARG parg;
  262.     if ((parg.p_string = re_comp(pattern)) != NULL)
  263.     {
  264.         error("%s", &parg);
  265.         return (-1);
  266.     }
  267.     re_pattern = 1;
  268. #endif
  269. #if HAVE_REGCMP
  270.     char *s;
  271.     if ((s = regcmp(pattern, 0)) == NULL)
  272.     {
  273.         error("Invalid pattern", NULL_PARG);
  274.         return (-1);
  275.     }
  276.     if (cpattern != NULL)
  277.         free(cpattern);
  278.     cpattern = s;
  279. #endif
  280. #if HAVE_V8_REGCOMP
  281.     struct regexp *s;
  282.     if ((s = regcomp(pattern)) == NULL)
  283.     {
  284.         /*
  285.          * regcomp has already printed error message via regerror().
  286.          */
  287.         return (-1);
  288.     }
  289.     if (regpattern != NULL)
  290.         free(regpattern);
  291.     regpattern = s;
  292. #endif
  293. #if NO_REGEX
  294.     static char lpbuf[100];
  295.     strcpy(lpbuf, pattern);
  296.     last_pattern = lpbuf;
  297. #endif
  298.     return (0);
  299. }
  300.  
  301. /*
  302.  * Forget that we have a compiled pattern.
  303.  */
  304.     static void
  305. uncompile_pattern()
  306. {
  307. #if HAVE_POSIX_REGCOMP
  308.     if (regpattern != NULL)
  309.         regfree(regpattern);
  310.     regpattern = NULL;
  311. #endif
  312. #if HAVE_RE_COMP
  313.     re_pattern = 0;
  314. #endif
  315. #if HAVE_REGCMP
  316.     if (cpattern != NULL)
  317.         free(cpattern);
  318.     cpattern = NULL;
  319. #endif
  320. #if HAVE_V8_REGCOMP
  321.     if (regpattern != NULL)
  322.         free(regpattern);
  323.     regpattern = NULL;
  324. #endif
  325. #if NO_REGEX
  326.     last_pattern = NULL;
  327. #endif
  328. }
  329.  
  330. /*
  331.  * Perform a pattern match with the previously compiled pattern.
  332.  * Set sp and ep to the start and end of the matched string.
  333.  */
  334.     static int
  335. match_pattern(line, sp, ep)
  336.     char *line;
  337.     char **sp;
  338.     char **ep;
  339. {
  340.     int matched;
  341. #if HAVE_POSIX_REGCOMP
  342.     regmatch_t rm;
  343.     matched = !regexec(regpattern, line, 1, &rm, 0);
  344.     if (!matched)
  345.         return (0);
  346.     *sp = line + rm.rm_so;
  347.     *ep = line + rm.rm_eo;
  348. #endif
  349. #if HAVE_RE_COMP
  350.     matched = (re_exec(line) == 1);
  351.     /*
  352.      * re_exec doesn't seem to provide a way to get the matched string.
  353.      */
  354.     *sp = *ep = NULL;
  355. #endif
  356. #if HAVE_REGCMP
  357.     *ep = regex(cpattern, line);
  358.     matched = (*ep != NULL);
  359.     if (!matched)
  360.         return (0);
  361.     *sp = __loc1;
  362. #endif
  363. #if HAVE_V8_REGCOMP
  364.     matched = regexec(regpattern, line);
  365.     if (!matched)
  366.         return (0);
  367.     *sp = regpattern->startp[0];
  368.     *ep = regpattern->endp[0];
  369. #endif
  370. #if NO_REGEX
  371.     matched = match(last_pattern, line, sp, ep);
  372. #endif
  373.     return (matched);
  374. }
  375.  
  376. #if HILITE_SEARCH
  377. /*
  378.  * Clear the hilite list.
  379.  */
  380.     public void
  381. clr_hilite()
  382. {
  383.     struct hilite *hl;
  384.     struct hilite *nexthl;
  385.  
  386.     for (hl = hilite_anchor.hl_next;  hl != NULL;  hl = nexthl)
  387.     {
  388.         nexthl = hl->hl_next;
  389.         free((void*)hl);
  390.     }
  391.     hilite_anchor.hl_next = NULL;
  392.     prep_startpos = prep_endpos = NULL_POSITION;
  393. }
  394.  
  395. /*
  396.  * Add a new hilite to the hilite list.
  397.  */
  398.     public void
  399. add_hilite(startpos, endpos)
  400.     POSITION startpos;
  401.     POSITION endpos;
  402. {
  403.     struct hilite *hl;
  404.     struct hilite *ihl;
  405.  
  406.     /*
  407.      * Hilites are sorted in the list; find where new one belongs.
  408.      * Insert new one after ihl.
  409.      */
  410.     for (ihl = &hilite_anchor;  ihl->hl_next != NULL;  ihl = ihl->hl_next)
  411.     {
  412.         if (ihl->hl_next->hl_startpos > startpos)
  413.             break;
  414.     }
  415.  
  416.     if (ihl != &hilite_anchor && startpos <= ihl->hl_endpos)
  417.     {
  418.         /*
  419.          * New hilite starts within existing ihl.
  420.          * Just extend ihl to end at the new hilite's end.
  421.          */
  422.         ihl->hl_endpos = MAXPOS(endpos, ihl->hl_endpos);
  423.     } else
  424.     {
  425.         /*
  426.          * Add new hilite after ihl.
  427.          */
  428.         hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
  429.         hl->hl_startpos = startpos;
  430.         /*
  431.          * If new hilite ends within the one after ihl,
  432.          * truncate it to end at the start of that one.
  433.          */
  434.         if (ihl->hl_next == NULL)
  435.             hl->hl_endpos = endpos;
  436.         else
  437.             hl->hl_endpos = MINPOS(endpos, ihl->hl_next->hl_startpos);
  438.         hl->hl_next = ihl->hl_next;
  439.         ihl->hl_next = hl;
  440.     }
  441. }
  442.  
  443. /*
  444.  * Should any characters in a specified range be highlighted?
  445.  * If nohide is nonzero, don't consider hide_hilite.
  446.  */
  447.     public int
  448. is_hilited(pos, epos, nohide)
  449.     POSITION pos;
  450.     POSITION epos;
  451.     int nohide;
  452. {
  453.     struct hilite *hl;
  454.  
  455.     if (hilite_search == 0)
  456.         /*
  457.          * Not doing highlighting.
  458.          */
  459.         return (0);
  460.  
  461.     if (!nohide && hide_hilite)
  462.         /*
  463.          * Highlighting is hidden.
  464.          */
  465.         return (0);
  466.  
  467.     /*
  468.      * Look at each highlight and see if any part of it falls in the range.
  469.      */
  470.     for (hl = hilite_anchor.hl_next;  hl != NULL;  hl = hl->hl_next)
  471.     {
  472.         if (hl->hl_endpos > pos &&
  473.             (epos == NULL_POSITION || epos > hl->hl_startpos))
  474.             return (1);
  475.     }
  476.     return (0);
  477. }
  478.  
  479. /*
  480.  * Adjust hl_startpos & hl_endpos to account for backspace processing.
  481.  */
  482.     static void
  483. adj_hilite(linepos)
  484.     POSITION linepos;
  485. {
  486.     char *line;
  487.     struct hilite *hl;
  488.     int checkstart;
  489.     POSITION opos;
  490.     POSITION npos;
  491.  
  492.     /*
  493.      * The line was already scanned and hilites were added (in hilite_line).
  494.      * But it was assumed that each char position in the line 
  495.      * correponds to one char position in the file.
  496.      * This may not be true if there are backspaces in the line.
  497.      * Get the raw line again.  Look at each character.
  498.      */
  499.     (void) forw_raw_line(linepos, &line);
  500.     opos = npos = linepos;
  501.     /*
  502.      * Find the first hilite in (or after) this line.
  503.      */
  504.     for (hl = hilite_anchor.hl_next;  hl != NULL;  hl = hl->hl_next)
  505.         if (hl->hl_startpos >= linepos)
  506.             break;
  507.     checkstart = 1;
  508.     while (hl != NULL)
  509.     {
  510.         /*
  511.          * See if we need to adjust the current hl_startpos or 
  512.          * hl_endpos.  After adjusting startpos[i], move to endpos[i].
  513.          * After adjusting endpos[i], move to startpos[i+1].
  514.          * The hilite list must be sorted thus: 
  515.          * startpos[0] < endpos[0] <= startpos[1] < endpos[1] <= etc.
  516.          */
  517.         if (checkstart && hl->hl_startpos == opos)
  518.         {
  519.             hl->hl_startpos = npos;
  520.             checkstart = 0;
  521.             continue; /* {{ not really necessary }} */
  522.         } else if (!checkstart && hl->hl_endpos == opos)
  523.         {
  524.             hl->hl_endpos = npos;
  525.             checkstart = 1;
  526.             hl = hl->hl_next;
  527.             continue; /* {{ necessary }} */
  528.         }
  529.         if (*line == '\0')
  530.             break;
  531.         opos++;
  532.         npos++;
  533.         line++;
  534.         if (line[0] == '\b' && line[1] != '\0')
  535.         {
  536.             /*
  537.              * Found a backspace.  The file position moves
  538.              * forward by 2 relative to the processed line
  539.              * which was searched in hilite_line.
  540.              */
  541.             npos += 2;
  542.             line += 2;
  543.         }
  544.     }
  545. }
  546.  
  547. /*
  548.  * Make a hilite for each string in a physical line which matches 
  549.  * the current pattern.
  550.  * sp,ep delimit the first match already found.
  551.  */
  552.     static void
  553. hilite_line(linepos, line, sp, ep)
  554.     POSITION linepos;
  555.     char *line;
  556.     char *sp;
  557.     char *ep;
  558. {
  559.     char *searchp;
  560.  
  561.     if (sp == NULL || ep == NULL)
  562.         return;
  563.     /*
  564.      * sp and ep delimit the first match in the line.
  565.      * Mark the corresponding file positions, then
  566.      * look for further matches and mark them.
  567.      * {{ This technique, of calling match_pattern on subsequent
  568.      *    substrings of the line, may mark more than is correct
  569.      *    if, for example, the pattern starts with "^". }}
  570.      */
  571.     searchp = line;
  572.     do {
  573.         if (ep > sp)
  574.         {
  575.             /*
  576.              * Assume that each char position in the "line"
  577.              * buffer corresponds to one char position in the file.
  578.              * This is not quite true; we need to adjust later.
  579.              */
  580.             add_hilite(linepos + (sp-line), linepos + (ep-line));
  581.         }
  582.         /*
  583.          * If we matched more than zero characters,
  584.          * move to the first char after the string we matched.
  585.          * If we matched zero, just move to the next char.
  586.          */
  587.         if (ep > searchp)
  588.             searchp = ep;
  589.         else if (*searchp != '\0')
  590.             searchp++;
  591.         else /* end of line */
  592.             break;
  593.     } while (match_pattern(searchp, &sp, &ep));
  594.  
  595.     if (bs_mode == BS_SPECIAL) 
  596.     {
  597.         /*
  598.          * If there were backspaces in the original line, they
  599.          * were removed, and hl_startpos/hl_endpos are not correct.
  600.          * {{ This is very ugly. }}
  601.          */
  602.         adj_hilite(linepos);
  603.     }
  604. }
  605. #endif
  606.  
  607. /*
  608.  * Change the caseless-ness of searches.  
  609.  * Updates the internal search state to reflect a change in the -i flag.
  610.  */
  611.     public void
  612. chg_caseless()
  613. {
  614.     if (!is_ucase_pattern)
  615.         /*
  616.          * Pattern did not have uppercase.
  617.          * Just set the search caselessness to the global caselessness.
  618.          */
  619.         is_caseless = caseless;
  620.     else
  621.         /*
  622.          * Pattern did have uppercase.
  623.          * Discard the pattern; we can't change search caselessness now.
  624.          */
  625.         uncompile_pattern();
  626. }
  627.  
  628. #if HILITE_SEARCH
  629. /*
  630.  * Find matching text which is currently on screen and highlight it.
  631.  */
  632.     static void
  633. hilite_screen()
  634. {
  635.     struct scrpos scrpos;
  636.  
  637.     get_scrpos(&scrpos);
  638.     if (scrpos.pos == NULL_POSITION)
  639.         return;
  640.     prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE));
  641.     repaint_hilite(1);
  642. }
  643.  
  644. /*
  645.  * Change highlighting parameters.
  646.  */
  647.     public void
  648. chg_hilite()
  649. {
  650.     /*
  651.      * Erase any highlights currently on screen.
  652.      */
  653.     clr_hilite();
  654.     hide_hilite = 0;
  655.  
  656.     if (hilite_search == OPT_ONPLUS)
  657.         /*
  658.          * Display highlights.
  659.          */
  660.         hilite_screen();
  661. }
  662. #endif
  663.  
  664. /*
  665.  * Figure out where to start a search.
  666.  */
  667.     static POSITION
  668. search_pos(search_type)
  669.     int search_type;
  670. {
  671.     POSITION pos;
  672.     int linenum;
  673.  
  674.     if (empty_screen())
  675.     {
  676.         /*
  677.          * Start at the beginning (or end) of the file.
  678.          * The empty_screen() case is mainly for 
  679.          * command line initiated searches;
  680.          * for example, "+/xyz" on the command line.
  681.          * Also for multi-file (SRCH_PAST_EOF) searches.
  682.          */
  683.         if (search_type & SRCH_FORW)
  684.         {
  685.             return (ch_zero());
  686.         } else
  687.         {
  688.             pos = ch_length();
  689.             if (pos == NULL_POSITION)
  690.             {
  691.                 (void) ch_end_seek();
  692.                 pos = ch_length();
  693.             }
  694.             return (pos);
  695.         }
  696.     }
  697.     if (how_search)
  698.     {
  699.         /*
  700.          * Search does not include current screen.
  701.          */
  702.         if (search_type & SRCH_FORW)
  703.             linenum = BOTTOM_PLUS_ONE;
  704.         else
  705.             linenum = TOP;
  706.         pos = position(linenum);
  707.     } else
  708.     {
  709.         /*
  710.          * Search includes current screen.
  711.          * It starts at the jump target (if searching backwards),
  712.          * or at the jump target plus one (if forwards).
  713.          */
  714.         linenum = adjsline(jump_sline);
  715.         pos = position(linenum);
  716.         if (search_type & SRCH_FORW)
  717.             pos = forw_raw_line(pos, (char **)NULL);
  718.     }
  719.     return (pos);
  720. }
  721.  
  722. /*
  723.  * Search a subset of the file, specified by start/end position.
  724.  */
  725.     static int
  726. search_range(pos, endpos, search_type, n, plinepos, pendpos)
  727.     POSITION pos;
  728.     POSITION endpos;
  729.     int search_type;
  730.     int n;
  731.     POSITION *plinepos;
  732.     POSITION *pendpos;
  733. {
  734.     char *line;
  735.     int linenum;
  736.     char *sp, *ep;
  737.     int line_match;
  738.     POSITION linepos, oldpos;
  739.  
  740.     linenum = find_linenum(pos);
  741.     oldpos = pos;
  742.     for (;;)
  743.     {
  744.         /*
  745.          * Get lines until we find a matching one or until
  746.          * we hit end-of-file (or beginning-of-file if we're 
  747.          * going backwards), or until we hit the end position.
  748.          */
  749.         if (ABORT_SIGS())
  750.         {
  751.             /*
  752.              * A signal aborts the search.
  753.              */
  754.             return (-1);
  755.         }
  756.  
  757.         if (endpos != NULL_POSITION && pos >= endpos)
  758.         {
  759.             /*
  760.              * Reached end position without a match.
  761.              */
  762.             if (pendpos != NULL)
  763.                 *pendpos = pos;
  764.             return (n);
  765.         }
  766.  
  767.         if (search_type & SRCH_FORW)
  768.         {
  769.             /*
  770.              * Read the next line, and save the 
  771.              * starting position of that line in linepos.
  772.              */
  773.             linepos = pos;
  774.             pos = forw_raw_line(pos, &line);
  775.             if (linenum != 0)
  776.                 linenum++;
  777.         } else
  778.         {
  779.             /*
  780.              * Read the previous line and save the
  781.              * starting position of that line in linepos.
  782.              */
  783.             pos = back_raw_line(pos, &line);
  784.             linepos = pos;
  785.             if (linenum != 0)
  786.                 linenum--;
  787.         }
  788.  
  789.         if (pos == NULL_POSITION)
  790.         {
  791.             /*
  792.              * Reached EOF/BOF without a match.
  793.              */
  794.             if (pendpos != NULL)
  795.                 *pendpos = NULL_POSITION;
  796.             return (n);
  797.         }
  798.  
  799.         /*
  800.          * If we're using line numbers, we might as well
  801.          * remember the information we have now (the position
  802.          * and line number of the current line).
  803.          * Don't do it for every line because it slows down
  804.          * the search.  Remember the line number only if
  805.          * we're "far" from the last place we remembered it.
  806.          */
  807.         if (linenums && abs((int)(pos - oldpos)) > 1024)
  808.         {
  809.             add_lnum(linenum, pos);
  810.             oldpos = pos;
  811.         }
  812.  
  813.         /*
  814.          * If it's a caseless search, convert the line to lowercase.
  815.          * If we're doing backspace processing, delete backspaces.
  816.          */
  817.         if (is_caseless || bs_mode == BS_SPECIAL)
  818.         {
  819.             int ops = 0;
  820.             if (is_caseless) 
  821.                 ops |= CVT_TO_LC;
  822.             if (bs_mode == BS_SPECIAL)
  823.                 ops |= CVT_BS;
  824.             cvt_text(line, line, ops);
  825.         }
  826.  
  827.         /*
  828.          * Test the next line to see if we have a match.
  829.          * We are successful if we either want a match and got one,
  830.          * or if we want a non-match and got one.
  831.          */
  832.         line_match = match_pattern(line, &sp, &ep);
  833.         line_match = (!(search_type & SRCH_NOMATCH) && line_match) ||
  834.                 ((search_type & SRCH_NOMATCH) && !line_match);
  835.         if (!line_match)
  836.             continue;
  837.         /*
  838.          * Got a match.
  839.          */
  840.         if (search_type & SRCH_FIND_ALL)
  841.         {
  842. #if HILITE_SEARCH
  843.             /*
  844.              * We are supposed to find all matches in the range.
  845.              * Just add the matches in this line to the 
  846.              * hilite list and keep searching.
  847.              */
  848.             if (line_match)
  849.                 hilite_line(linepos, line, sp, ep);
  850. #endif
  851.         } else if (--n <= 0)
  852.         {
  853.             /*
  854.              * Found the one match we're looking for.
  855.              * Return it.
  856.              */
  857. #if HILITE_SEARCH
  858.             if (hilite_search == 1)
  859.             {
  860.                 /*
  861.                  * Clear the hilite list and add only
  862.                  * the matches in this one line.
  863.                  */
  864.                 clr_hilite();
  865.                 if (line_match)
  866.                     hilite_line(linepos, line, sp, ep);
  867.             }
  868. #endif
  869.             if (plinepos != NULL)
  870.                 *plinepos = linepos;
  871.             return (0);
  872.         }
  873.     }
  874. }
  875.  
  876. /*
  877.  * Search for the n-th occurrence of a specified pattern, 
  878.  * either forward or backward.
  879.  * Return the number of matches not yet found in this file
  880.  * (that is, n minus the number of matches found).
  881.  * Return -1 if the search should be aborted.
  882.  * Caller may continue the search in another file 
  883.  * if less than n matches are found in this file.
  884.  */
  885.     public int
  886. search(search_type, pattern, n)
  887.     int search_type;
  888.     char *pattern;
  889.     int n;
  890. {
  891.     POSITION pos;
  892.     int ucase;
  893.  
  894.     if (pattern == NULL || *pattern == '\0')
  895.     {
  896.         /*
  897.          * A null pattern means use the previously compiled pattern.
  898.          */
  899.         if (!prev_pattern())
  900.         {
  901.             error("No previous regular expression", NULL_PARG);
  902.             return (-1);
  903.         }
  904. #if HILITE_SEARCH
  905.         if (hilite_search == 1)
  906.         {
  907.             /*
  908.              * Erase the highlights currently on screen.
  909.              * If the search fails, we'll redisplay them later.
  910.              */
  911.             repaint_hilite(0);
  912.             hide_hilite = 0;
  913.         }
  914. #endif
  915.     } else
  916.     {
  917.         /*
  918.          * Compile the pattern.
  919.          */
  920.         ucase = is_ucase(pattern);
  921.         if (caseless == OPT_ONPLUS)
  922.             cvt_text(pattern, pattern, CVT_TO_LC);
  923.         if (compile_pattern(pattern) < 0)
  924.             return (-1);
  925.         /*
  926.          * Ignore case if -I is set OR
  927.          * -i is set AND the pattern is all lowercase.
  928.          */
  929.         is_ucase_pattern = ucase;
  930.         if (is_ucase_pattern && caseless != OPT_ONPLUS)
  931.             is_caseless = 0;
  932.         else
  933.             is_caseless = caseless;
  934. #if HILITE_SEARCH
  935.         if (hilite_search)
  936.         {
  937.             /*
  938.              * Erase the highlights currently on screen.
  939.              * Also permanently delete them from the hilite list.
  940.              */
  941.             repaint_hilite(0);
  942.             hide_hilite = 0;
  943.             clr_hilite();
  944.         }
  945.         if (hilite_search == OPT_ONPLUS)
  946.         {
  947.             /*
  948.              * Highlight any matches currently on screen,
  949.              * before we actually start the search.
  950.              */
  951.             hilite_screen();
  952.         }
  953. #endif
  954.     }
  955.  
  956.     /*
  957.      * Figure out where to start the search.
  958.      */
  959.     pos = search_pos(search_type);
  960.     if (pos == NULL_POSITION)
  961.     {
  962.         /*
  963.          * Can't find anyplace to start searching from.
  964.          */
  965.         if (search_type & SRCH_PAST_EOF)
  966.             return (n);
  967.         error("Nothing to search", NULL_PARG);
  968.         return (-1);
  969.     }
  970.  
  971.     n = search_range(pos, NULL_POSITION, search_type, n, 
  972.             &pos, (POSITION*)NULL);
  973.     if (n != 0)
  974.     {
  975.         /*
  976.          * Search was unsuccessful.
  977.          */
  978. #if HILITE_SEARCH
  979.         if (hilite_search == OPT_ON && n > 0)
  980.             /*
  981.              * Redisplay old hilites.
  982.              */
  983.             repaint_hilite(1);
  984. #endif
  985.         return (n);
  986.     }
  987.  
  988.     /*
  989.      * Go to the matching line.
  990.      */
  991.     jump_loc(pos, jump_sline);
  992.  
  993. #if HILITE_SEARCH
  994.     if (hilite_search == OPT_ON)
  995.         /*
  996.          * Display new hilites in the matching line.
  997.          */
  998.         repaint_hilite(1);
  999. #endif
  1000.     return (0);
  1001. }
  1002.  
  1003. #if HILITE_SEARCH
  1004. /*
  1005.  * Prepare hilites in a given range of the file.
  1006.  *
  1007.  * The pair (prep_startpos,prep_endpos) delimits a contiguous region
  1008.  *  of the file that has been "prepared"; that is, scanned for matches for
  1009.  * the current search pattern, and hilites have been created for such matches.
  1010.  * If prep_startpos == NULL_POSITION, the prep region is empty.
  1011.  * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
  1012.  * prep_hilite asks that the range (spos,epos) be covered by the prep region.
  1013.  */
  1014.     public void
  1015. prep_hilite(spos, epos)
  1016.     POSITION spos;
  1017.     POSITION epos;
  1018. {
  1019.     POSITION nprep_startpos = prep_startpos;
  1020.     POSITION nprep_endpos = prep_endpos;
  1021. /*
  1022.  * Search beyond where we're asked to search, so the prep region covers
  1023.  * more than we need.  Do one big search instead of a bunch of small ones.
  1024.  */
  1025. #define    SEARCH_MORE (3*size_linebuf)
  1026.  
  1027.     if (!prev_pattern())
  1028.         return;
  1029.     /*
  1030.      * Find two ranges:
  1031.      * The range that we need to search (spos,epos); and the range that
  1032.      * the "prep" region will then cover (nprep_startpos,nprep_endpos).
  1033.      */
  1034.  
  1035.     if (prep_startpos == NULL_POSITION ||
  1036.         (epos != NULL_POSITION && epos < prep_startpos) ||
  1037.         (prep_endpos != NULL_POSITION && spos > prep_endpos))
  1038.     {
  1039.         /*
  1040.          * New range is not contiguous with old prep region.
  1041.          * Discard the old prep region and start a new one.
  1042.          */
  1043.         clr_hilite();
  1044.         if (epos != NULL_POSITION)
  1045.             epos += SEARCH_MORE;
  1046.         nprep_startpos = spos;
  1047.         nprep_endpos = epos;
  1048.     } else
  1049.     {
  1050.         /*
  1051.          * New range partially or completely overlaps old prep region.
  1052.          */
  1053.         if (epos == NULL_POSITION)
  1054.         {
  1055.             /*
  1056.              * New range goes to end of file.
  1057.              */
  1058.             nprep_endpos = NULL_POSITION;
  1059.         } else if (epos > prep_endpos)
  1060.         {
  1061.             /*
  1062.              * New range ends after old prep region.
  1063.              * Extend prep region to end at end of new range.
  1064.              */
  1065.             epos += SEARCH_MORE;
  1066.             nprep_endpos = epos;
  1067.         } else /* (epos <= prep_endpos) */
  1068.         {
  1069.             /*
  1070.              * New range ends within old prep region.
  1071.              * Truncate search to end at start of old prep region.
  1072.              */
  1073.             epos = prep_startpos;
  1074.         }
  1075.  
  1076.         if (spos < prep_startpos)
  1077.         {
  1078.             /*
  1079.              * New range starts before old prep region.
  1080.              * Extend old prep region backwards to start at 
  1081.              * start of new range.
  1082.              */
  1083.             if (spos < SEARCH_MORE)
  1084.                 spos = 0;
  1085.             else
  1086.                 spos -= SEARCH_MORE;
  1087.             nprep_startpos = spos;
  1088.         } else /* (spos >= prep_startpos) */
  1089.         {
  1090.             /*
  1091.              * New range starts within or after old prep region.
  1092.              * Trim search to start near end of old prep region
  1093.              * (actually, one linebuf before end of old range).
  1094.              */
  1095.             if (prep_endpos == NULL_POSITION)
  1096.                 return;
  1097.             else if (prep_endpos < size_linebuf)
  1098.                 spos = 0;
  1099.             else 
  1100.                 spos = prep_endpos - size_linebuf;
  1101.         }
  1102.     }
  1103.  
  1104.     if (epos == NULL_POSITION || epos > spos)
  1105.     {
  1106.         if (search_range(spos, epos, SRCH_FORW|SRCH_FIND_ALL, 0,
  1107.                 (POSITION*)NULL, &epos) >= 0)
  1108.         {
  1109.             if (epos == NULL_POSITION || epos > nprep_endpos)
  1110.                 nprep_endpos = epos;
  1111.         }
  1112.     }
  1113.     prep_startpos = nprep_startpos;
  1114.     prep_endpos = nprep_endpos;
  1115. }
  1116. #endif
  1117.  
  1118. #if NO_REGEX
  1119. /*
  1120.  * We have no pattern matching function from the library.
  1121.  * We use this function to do simple pattern matching.
  1122.  * It supports no metacharacters like *, etc.
  1123.  */
  1124.     static int
  1125. match(pattern, buf, pfound, pend)
  1126.     char *pattern, *buf;
  1127.     char **pfound, **pend;
  1128. {
  1129.     register char *pp, *lp;
  1130.  
  1131.     for ( ;  *buf != '\0';  buf++)
  1132.     {
  1133.         for (pp = pattern, lp = buf;  *pp == *lp;  pp++, lp++)
  1134.             if (*pp == '\0' || *lp == '\0')
  1135.                 break;
  1136.         if (*pp == '\0')
  1137.         {
  1138.             if (pfound != NULL)
  1139.                 *pfound = buf;
  1140.             if (pend != NULL)
  1141.                 *pend = lp;
  1142.             return (1);
  1143.         }
  1144.     }
  1145.     return (0);
  1146. }
  1147. #endif
  1148.  
  1149. #if HAVE_V8_REGCOMP
  1150. /*
  1151.  * This function is called by the V8 regcomp to report 
  1152.  * errors in regular expressions.
  1153.  */
  1154.     void 
  1155. regerror(s) 
  1156.     char *s; 
  1157. {
  1158.     PARG parg;
  1159.  
  1160.     parg.p_string = s;
  1161.     error("%s", &parg);
  1162. }
  1163. #endif
  1164.  
  1165. #if !HAVE_STRCHR
  1166. /*
  1167.  * strchr is used by regexp.c.
  1168.  */
  1169.     char *
  1170. strchr(s, c)
  1171.     char *s;
  1172.     int c;
  1173. {
  1174.     for ( ;  *s != '\0';  s++)
  1175.         if (*s == c)
  1176.             return (s);
  1177.     if (c == '\0')
  1178.         return (s);
  1179.     return (NULL);
  1180. }
  1181. #endif
  1182.  
  1183.